package codetop.greedy;

public class Code316 {
    public String removeDuplicateLetters(String s) {
        int len=s.length();
        int nums[]=new int[26];//保存每个字母出现的次数
        boolean used[]=new boolean[26];
        for (int i = 0; i < len; i++) {
            char c=s.charAt(i);
            nums[c-'a']++;
        }
        StringBuilder sb=new StringBuilder();
        for (int i = 0; i < len; i++) {
            char c=s.charAt(i);
            while (!used[c]){
                while (sb.length()>0&&sb.charAt(sb.length()-1)>c){
                    if (nums[sb.charAt(sb.length()-1)-'a']>0){
                        used[sb.charAt(sb.length()-1)-'a']=false;
                        sb.deleteCharAt(sb.length()-1);
                    }
                    else {
                        break;
                    }
                }
                used[c - 'a'] = true;
                sb.append(c);
            }
            nums[c-'a']--;
        }
        return sb.toString();
    }
}
